/**
 * 279. 完全平方数
 * https://leetcode-cn.com/problems/perfect-squares/
 */

/**
 * @param {number} target
 * @param {number[]} nums
 * @param {number} length
 * @return {number}
 */
function findIndex(target, nums, length) {
  let left = 0;
  let right = length - 1;
  while (left <= right) {
    const middle = Math.floor((left + right) / 2);
    if (target === nums[middle]) {
      return middle;
    }
    if (nums[middle] < target) {
      if (middle >= length - 1 || nums[middle + 1] > target) {
        return middle;
      }
      left = middle + 1;
    } else {
      right = middle - 1;
    }
  }
  return -1;
}

/**
 * @param {number} n
 * @return {number}
 */
function numSquares(n) {
  const maxSqrt = Math.floor(Math.sqrt(n));
  const squares = new Array(maxSqrt);
  for (let i = 1; i <= maxSqrt; i += 1) {
    squares[i - 1] = i * i;
  }
  const dp = new Array(n + 1);
  for (let i = 0; i <= n; i += 1) {
    dp[i] = new Array(maxSqrt + 1).fill(0);
  }
  for (let i = 1; i <= n; i += 1) {
    for (let j = 1; j <= maxSqrt; j += 1) {
      const index = findIndex(i, squares, j);
      if (index <= 0) {
        dp[i][j] = dp[i - squares[index]][j] + 1;
      } else {
        dp[i][j] = Math.min(dp[i - squares[index]][j] + 1, dp[i][index]);
      }
    }
  }
  return dp[n][maxSqrt];
}

console.log(numSquares(12) === 3);
console.log(numSquares(13) === 2);
